package it.luigiarpino.kernighanLin;

import it.luigiarpino.kernighanLin.bipartition.LKBipartitionEnhanced;


/**
 * Effettua un k-partizionamento di un grafo
 * 
 * precondizioni:
 *    matrice quadrata di dimensione n*n
 *    n = k * i ; con n,k,i interi 
 *    
 * @author Luigi Lorenzo Arpino [luigiarpino@yahoo.it]
 *
 */
public class KPartitioning 
{
	public static void main(String args[])
	{
		/*
		int[][] matrix={
			    //   0  1  2  3  4  5  6  7
					{0, 0, 1, 0, 0, 0, 0, 0 },// 0
					{0, 0, 1, 0, 0, 0, 0, 0 },// 1
					{1, 1, 0, 1, 1, 0, 0, 0 },// 2
					{0, 0, 1, 0, 0, 0, 0, 0 },// 3
					{0, 0, 1, 0, 0, 1, 1, 1 },// 4
					{0, 0, 0, 0, 1, 0, 0, 0 },// 5
					{0, 0, 0, 0, 1, 0, 0, 0 },// 6
					{0, 0, 0, 0, 1, 0, 0, 0 },// 7
			};
		*/
		/*
		int[][] matrix={
			    //   0  1  2  3  4  5  6  7  8
					{0, 0, 0, 1, 0, 0, 0, 0, 1 },// 0
					{0, 0, 0, 0, 1, 0, 1, 1, 1 },// 1
					{0, 0, 0, 0, 0, 1, 1, 0, 0 },// 2
					{1, 0, 0, 0, 0, 0, 0, 0, 1 },// 3
					{0, 1, 0, 0, 0, 0, 0, 1, 0 },// 4
					{0, 0, 1, 0, 0, 0, 1, 0, 0 },// 5
					{0, 1, 1, 0, 0, 1, 0, 0, 1 },// 6
					{0, 1, 0, 0, 1, 0, 0, 0, 0 },// 7
					{1, 1, 0, 1, 0, 0, 1, 0, 0 },// 8
			};
			*/
		int[][] matrix={
			    //   0  1  2  3  4  5  
					{0, 1, 1, 1, 0, 0 },//0
					{1, 0, 0, 0, 0, 0 },//1
					{1, 0, 0, 0, 0, 0 },//2
					{1, 0, 0, 0, 0, 0 },//3
					{0, 0, 0, 0, 0, 0 },//4
					{0, 0, 0, 0, 0, 0 },//5
			};
		
		//KPartitioning kp=new KPartitioning(matrix,4);
		KPartitioning kp=new KPartitioning(matrix,2);
		int[] partizionamento=kp.getPartizionamento();
		int costo = kp.getCosto();
		System.out.println();
		System.out.println("Costo="+costo);
		System.out.println();
		System.out.println("Partizionamento");
		for(int i=0; i< partizionamento.length ; i++)
	    {
			System.out.print(" "+partizionamento[i]);
	    }
		
		
	}
	
	private int[][]matrix;
	private int numeroPartizioni;
	private int[] partizionamento;
	private int[] vector;
	private int NUM_CICLI=2; // il numero di minimi locali  
	
	
	
	public KPartitioning(int[][] matrice, int k)
	{
		this.matrix=matrice;
		this.numeroPartizioni=k;
		
		this.inizializzaPartizionamento();
		int oldCosto=0;
		int nuovoCosto=0;
		boolean isFirstCycle=true;
		while (isFirstCycle || nuovoCosto < oldCosto)
		{
			if (isFirstCycle)
			{
				this.calcola();
				oldCosto=this.getCosto();
				nuovoCosto=oldCosto;
				oldCosto ++;
				isFirstCycle=false;
			}
			else
			{
				oldCosto=nuovoCosto;
				this.calcola();
				nuovoCosto=this.getCosto();
			}
		}
	}
	
	private void calcolaParizionamento(int set1, int set2 )
	{
		int[][] sottoMatrce=this.getMatriceDiAdiacenza(set1, set2);
		LKBipartitionEnhanced lk = new LKBipartitionEnhanced(sottoMatrce, NUM_CICLI);
		int[] optA=lk.getOptimalPartitionA();
		int[] optB=lk.getOptimalPartitionB();
		// aggiusto il partizionamento
		for (int i=0; i<optA.length;i++)
		{
			int index=this.vector[optA[i]];
			this.partizionamento[index]=set1;
		}
		for (int i=0; i<optB.length;i++)
		{
			int index=this.vector[optB[i]];
			this.partizionamento[index]=set2;
		}	
	}
	/*
	private void printVettore(String descrizione, int[] vett)
	{
		System.out.println();
		System.out.println(descrizione);
		for(int i=0; i<vett.length ; i++)
		{
			System.out.print(" "+vett[i]);
		}
		System.out.println();
	}
	*/
	private void printPartizionamento()
	{
		System.out.println();
		System.out.println("Partizionamento:");
		for(int i=0; i<this.partizionamento.length ; i++)
		{
			System.out.print(" "+partizionamento[i]);
		}
		System.out.println();
	}
	
	private void printMatrix(String description, int[][] matrix)
	{
		System.out.println();
		System.out.println(description);
		for(int i=0; i<matrix.length ; i++)
		{
			for(int j=0; j<matrix.length ; j++)
			{
				System.out.print(" "+matrix[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}
	
	private int[] getPartizione(int node)
	{
		int dimPartizione=matrix.length/this.numeroPartizioni;
		int[] partizione=new int[dimPartizione];
		int index=0;
		for(int i=0; i<partizionamento.length; i++)
		{
			if(partizionamento[i]==node)
			{
				partizione[index]=i;
				index ++;
			}
		}
		return partizione;
	}
	

	
	/**
	 * Restituisce la matrice di adiacenza relativa
	 * agli insemi set1 e set2
	 * 
	 * @param set1
	 * @param set2
	 * @return
	 */
	public int[][] getMatriceDiAdiacenza(int set1 , int set2)
	{
		int dimPartizione=matrix.length/this.numeroPartizioni;
		
		// costruisco la nuova matrice
		int[] partA=getPartizione(set1);
		int[] partB=getPartizione(set2);
		int dimMatrice=partA.length+partB.length;
		vector=new int[dimMatrice];
		for(int i=0; i< partA.length; i++)
		{
			vector[i]=partA[i];
			vector[i+dimPartizione]=partB[i];
		}
		// inizializzo la matrice
		int [][] matrice=new int[dimMatrice][dimMatrice];
		for(int i=0 ; i<dimMatrice; i++)
		{
			for(int j=0 ; j<dimMatrice; j++)
			{
				int indexA=vector[i];
				int indexB=vector[j];
				matrice[i][j]=matrix[indexA][indexB];
			}
		}
		return matrice;
	}
	/*
	public int[][] getMatriceAdiacenza(int node1 , int node2)
	{
		int dimPartizione=matrix.length/this.numeroPartizioni;
		// inizializzo la matrice
		int [][] matrice=new int[dimPartizione][dimPartizione];
		for(int i=0 ; i<dimPartizione; i++)
		{
			for(int j=0 ; j<dimPartizione; j++)
			{
				matrice[i][j]=0;
			}
		}
		// riempio la matrice
		Set<Integer> set1=this.lista.get(node1);
		Set<Integer> set2=this.lista.get(node2);
		for(Object object1: set1.toArray() )
		{
			int value1=((Integer)object1).intValue();
			for(Object object2: set2.toArray() )
			{
				int value2=((Integer)object2).intValue();
				
			}
		}
		return null;
	}
	*/
	
	private void calcola()
	{
		for (int i=0; i<this.numeroPartizioni ; i++)
		{
			for (int j=i+1; j<this.numeroPartizioni ; j++)
			{
				if (i != j)
				{
					this.calcolaParizionamento(i, j);
				}
			}
		}
		
	}
	
	/**
	 * Restituisce il costo della partizione
	 * 
	 * @return
	 */
	public int getCosto()
	{
		int costo=0;
		for (int i=0; i<this.numeroPartizioni ; i++)
		{
			for (int j=i+1; j<this.numeroPartizioni ; j++)
			{
				if (i != j)
				{
					costo += this.getCostoTaglio(i, j);
				}
			}
		}
		return costo;
	}
	
	public int getCostoMaxTaglio()
	{
		int costo=0;
		for (int i=0; i<this.numeroPartizioni ; i++)
		{
			for (int j=i+1; j<this.numeroPartizioni ; j++)
			{
				if (i != j)
				{
					int costoTaglio=this.getCostoTaglio(i, j);
					if(  costoTaglio>costo)
					{
						costo = costoTaglio;
					}
				}
			}
		}
		return costo;
	}
	
	private int getCostoTaglio(int set1, int set2)
	{
		int dimPartizione=matrix.length/this.numeroPartizioni;
		// calcolo l'insieme set1
		int[] partitionA=new int[dimPartizione];
		int[] partitionB=new int[dimPartizione];
		int ka=0;
		int kb=0;
		for (int i=0 ;i<this.partizionamento.length ; i++)
		{
			if (this.partizionamento[i]==set1)
			{
				partitionA[ka]=i;
				ka++;
			}
			else if (this.partizionamento[i]==set2)
			{
				partitionB[kb]=i;
				kb++;
			}
		}
		// calcolo il costo
		int costo = 0;
		for (int i=0 ; i <partitionA.length ; i++)
		{
			for(int j=0 ; j< partitionB.length ; j++ )
			{
				int a=partitionA[i];
				int b=partitionB[j];
				int wab=matrix[a][b];
				costo += wab; 
			}
		}
		return costo;
	}
	
	
	public int[] getPartizionamento()
	{
		return this.partizionamento;
	}
	
	
	
	private void inizializzaPartizionamento()
	{
		this.partizionamento=new int[matrix.length];
		int dimPartizione=matrix.length/this.numeroPartizioni;
		for(int i=0; i<this.numeroPartizioni ; i++)
		{
			for(int j=0; j<dimPartizione; j++)
			{
				this.partizionamento[(i*dimPartizione)+j]=i;
			}
		}
	}
	
}
